# Copyright (C) 2012 by Sean Sherrard.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#      http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

__author__ = 'Sean Sherrard'
__version__ = '1.2'
__copyright__ = "Copyright 2012, Sean Sherrard"

import math
import codecs
import re
from cStringIO import StringIO
from binascii import hexlify, unhexlify
from datetime import date, time, datetime, timedelta, tzinfo
from time import tzname, daylight, timezone, altzone

USE_LOGGING = True
if USE_LOGGING:
	import logging
	log = logging.getLogger(__name__)

if True:
	from pprint import PrettyPrinter
	class MyPrinter(PrettyPrinter):
		def format(self, object, context, maxlevels, level):
			r = repr(object)
			if len(r) > self._width:
				return r[:self._width-4]+'...'+r[-1], False, False
			else:
				return PrettyPrinter.format(self, object, context, maxlevels, level)
	pr = MyPrinter(width=60).pprint

# ===========================================================================

# ASN.1 Tag Classes and Universal Tag Numbers

UNIVERSAL = 0
APPLICATION = 1
CONTEXT = 2
PRIVATE = 3

EOC =               0 # End-Of-Contruction sentinel
BOOLEAN =           1 # bool
INTEGER =           2 # int or long
BIT_STRING =        3 # BitString
OCTET_STRING =      4 # bytes
NULL =              5 # None
OBJECT_IDENTIFIER = 6 # ObjectID
OBJECT_DESCRIPTOR = 7 # string
EXTERNAL =          8 # EmbeddedValue
REAL =              9 # float
ENUMERATED =       10 # Enumerated
EMBEDDED_PDV =     11 # EmbeddedValue
UTF8_STRING =      12 # string
RELATIVE_OID =     13 # ObjectID
TIME =             14 # string
SEQUENCE =         16 # Sequence, list or tuple
SET =              17 # Set, set or frozenset
NUMERIC_STRING =   18 # string
PRINTABLE_STRING = 19 # string
TELETEX_STRING =   20 # string
T61_STRING = TELETEX_STRING
VIDEOTEX_STRING =  21 # string
IA5_STRING =       22 # string
UTC_TIME =         23 # datetime with tzinfo == UTC
GENERALIZED_TIME = 24 # datetime with tzinfo != UTC
GRAPHIC_STRING =   25 # string
VISIBLE_STRING =   26 # string
ISO646_STRING = VISIBLE_STRING
GENERAL_STRING =   27 # string
UNIVERSAL_STRING = 28 # string
CHARACTER_STRING = 29 # EmbeddedValue
BMP_STRING =       30 # string
DATE =             31 # date
TIME_OF_DAY =      32 # time
DATE_TIME =        33 # datetime without tzinfo
DURATION =         34 # string
OID_IRI =          35 # string
RELATIVE_OID_IRI = 36 # string

# ===========================================================================

# ASN.1 Serialization Functions

def dump(obj, file, encoding='BER', strtype=None, segsize=None):
	if encoding not in ('BER', 'DER', 'CER'):
		raise ValueError('invalid ASN.1 encoding: {}'.format(encoding))
	if strtype is not None and strtype not in _string_map:
		raise ValueError('invalid ASN.1 string type: {}'.format(strtype))
	if segsize is not None and (encoding != 'BER' or not (1 <= segsize <= 2147483647)):
		raise ValueError('invalid ASN.1 segment size for {} encoding'.format(encoding))
	if encoding == 'CER':
		segsize = 1000
	itemlen, itemval = _encode_item(obj, encoding, strtype, segsize)
	def dumpelem(elem):
		ident, length, content = elem
		file.write(ident)
		file.write(length)
		if isinstance(content, bytes):
			file.write(content)
		else:
			for elem in content:
				dumpelem(elem)
	dumpelem(itemval)

def dumps(obj, encoding='BER', strtype=None, segsize=None):
	file = StringIO()
	dump(obj, file, encoding, strtype, segsize)
	return file.getvalue()

def load(file, encoding='BER', strict=True):
	if encoding not in ('BER', 'DER', 'CER'):
		raise ValueError('invalid ASN.1 encoding: {}'.format(encoding))
	length, item = _decode_item(file, 0, encoding, strict)
	# XXX verify that we're at the EOF? pickle doesn't but json does
	if strict and file.read(1) != b'':
		_decode_error(length, strict, 'extra data')
#	if offset != len(data):
#		_decode_error(strict, 'value length', offset)
	return item

def loads(data, encoding='BER', strict=True):
	if not isinstance(data, bytes):
		raise TypeError('invalid ASN.1 encoded value')
	file = StringIO(data)
	return load(file, encoding, strict)

# ===========================================================================

# ASN.1 Character String Definitions

def _restricted_codec(name, chars):
	INVALID = u'\uFFFE'
	decoding_table = (u''.join([INVALID for i in xrange(0x00, 0x20)]) +
					  u''.join([unichr(i) if (chars is None or chr(i) in chars) else INVALID
								for i in xrange(0x20, 0x7F)]) +
					  u''.join([INVALID for i in xrange(0x7F, 0x100)]))
	encoding_table = codecs.charmap_build(decoding_table)
	def encode(input, errors='strict'):
		return codecs.charmap_encode(input, errors, encoding_table)
	def decode(input, errors='strict'):
		return codecs.charmap_decode(input, errors, decoding_table)
	_codec_map[name] = codecs.CodecInfo(name=name, encode=encode, decode=decode)

def _teletex_codec(name):
	INVALID = u'\uFFFE'
	decoding_table = [unichr(i) for i in xrange(256)]
	for i in (35, 36, 92, 94, 96, 123, 125, 126, 169, 170, 172, 173, 174, 175, 185, 186):
		decoding_table[i] = INVALID
	decoding_table[164] = u'$'
	decoding_table[166] = u'#'
	decoding_table[168] = u'\u00A4'
	decoding_table[180] = u'\u00D7'
	decoding_table[184] = u'\u00F7'
	for idx, chr in enumerate(u'\uFFFE\u0300\u0301\u0302\u0303\u0304\u0306\u0307'
							  u'\u0308\uFFFE\u030A\u0327\u0332\u030B\u0328\u030C' + 
							  INVALID*16 +
							  u'\u2126\u00C6\u00D0\u00AA\u0126\uFFFE\u0132\u013F'
							  u'\u0141\u00D8\u0152\u00BA\u00DE\u0166\u014A\u0149'
							  u'\u0138\u00E6\u0111\u00F0\u0127\u0131\u0133\u0140'
							  u'\u0142\u00F8\u0153\u00DF\u00FE\u0167\u014B\uFFFE'):
		decoding_table[192+idx] = chr
	decoding_table = u''.join(decoding_table)
	encoding_table = codecs.charmap_build(decoding_table)
	def encode(input, errors='strict'):
		return codecs.charmap_encode(input, errors, encoding_table)
	def decode(input, errors='strict'):
		return codecs.charmap_decode(input, errors, decoding_table)
	_codec_map[name] = codecs.CodecInfo(name=name, encode=encode, decode=decode)

def _deferred_codec(name, other):
	_deferred_codec.other = None
	def encode(input, errors='strict'):
		if _deferred_codec.other or max(input) > u'\x7F':
			_deferred_codec.other = _deferred_codec.other or codecs.lookup(other)
			return _deferred_codec.other.encode(input, errors)
		else:
			return codecs.ascii_encode(input, errors)
	def decode(input, errors='strict'):
		if _deferred_codec.other or b'\x1B' in input:
			_deferred_codec.other = _deferred_codec.other or codecs.lookup(other)
			return _deferred_codec.other.decode(input, errors)
		else:
			return codecs.ascii_decode(input, errors)
	_codec_map[name] =  codecs.CodecInfo(name=name, encode=encode, decode=decode)

def _string_type(name, tag, encoding):
	cls = type(name, (unicode,), {'__slots__': [], 'tag': tag, 'encoding': encoding})
	_string_map[tag] = cls
	globals()[name] = cls

_codec_map = {}
_restricted_codec('numeric-string', "0123456789 ")
_restricted_codec('printable-string', "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
									  "abcdefghijklmnopqrstuvwxyz"
									  "0123456789 '()+,-./:=?")
_restricted_codec('visible-string', None)
_teletex_codec('teletex')
codecs.register(_codec_map.get)

_string_map = {}
_string_type('NumericString',   NUMERIC_STRING,   'numeric-string')
_string_type('PrintableString', PRINTABLE_STRING, 'printable-string')
_string_type('VisibleString',   VISIBLE_STRING,   'visible-string')
_string_type('IA5String',       IA5_STRING,       'ascii')
_string_type('TeletexString',   TELETEX_STRING,   'teletex')
_string_type('VideotexString',  VIDEOTEX_STRING,  'teletex')
_string_type('GraphicString',   GRAPHIC_STRING,   'latin-1')
_string_type('GeneralString',   GENERAL_STRING,   'latin-1')
_string_type('UTF8String',      UTF8_STRING,      'utf-8')
_string_type('BMPString',       BMP_STRING,       'utf-16-be')
_string_type('UniversalString', UNIVERSAL_STRING, 'utf-32-be')
_string_type('ObjectDescriptor',OBJECT_DESCRIPTOR,'latin-1')
_string_type('TimeString',      TIME,             'utf-8')

# ===========================================================================

# ASN.1 Date and Time Definitions

_datetime_map = {UTC_TIME:         ('%y%m%d%H%M%S', 12, True),
				 GENERALIZED_TIME: ('%Y%m%d%H%M%S', 14, True),
				 DATE:             ('%Y%m%d', None, False),
				 TIME_OF_DAY:      ('%H%M%S', None, False),
				 DATE_TIME:        ('%Y%m%d%H%M%S', None, False)}

_duration_re = re.compile(r'(?:(\d+)W)?(?:(\d+)D)?(?:T(?:(\d+)H)?(?:(\d+)M)?(?:(\d+)S)?)?')

class TimeZone(tzinfo):
	__slots__ = ['_name', '_offset']
	ZERO = timedelta(0)
	def __init__(self, tzname, tzoffset):
		self._name = tzname
		self._offset = timedelta(minutes=tzoffset)
#	def __repr__(self):
#		return repr(self._name)
	def utcoffset(self, dt):
		return self._offset
	def dst(self, dt):
		return TimeZone.ZERO
	def tzname(self, dt):
		return self._name
	@staticmethod
	def split(value):
		if value[-1:] == 'Z':
			return value[:-1], TimeZone.Zulu
		elif value[-5:-4] in ('-', '+'):
			tzm = int(value[-5]+'1')*(int(value[-4:-2])*60 + int(value[-2:]))
			return value[:-5], TimeZone(value[-5:], tzm)
		else:
			return value, None

TimeZone.UTC = TimeZone('UTC', 0)
TimeZone.Zulu = TimeZone('Z', 0)
TimeZone.Local = TimeZone(tzname[daylight], -(timezone, altzone)[daylight]//60)

# ===========================================================================

# ASN.1 Object Subtype Definitions

class IRIString(unicode):
	__slots__ = []

class BitString(bytes):
#	__slots__ = ['pad']  # can't have slots on str subclasses
	def __new__(cls, val, pad=0):
		if pad < 0 or pad > 7 or (pad and not val):
			raise ValueError('invalid BitString pad value')
		self = bytes.__new__(cls, val)
		self.pad = pad
		return self
	def __index__(self):
		return btoul(self)
	def __hex__(self):
		return '0x' + hexlify(self)
	def bit_length(self):
		return len(self)*8 - self.pad

class Enumerated(int):
	__slots__ = []

class ObjectID(object):
	__slots__ = ['_value']
	def __new__(cls, *args):
		if not args:
			raise TypeError('ObjectID can not be null')
		value = ()
		for part in args[:-1]:
			if isinstance(part, ObjectID):
				part = part._value if part._value[0] is not None else part._value[1:]
			value += tuple(part)
		part = args[-1]
		if isinstance(part, basestring):
			part = [int(x) if x else None for x in part.split('.')]
		value += tuple(part)
		if len(value) < 2:
			raise ValueError('ObjectID must have at least 2 components')
		self = object.__new__(cls)
		self._value = value
		return self
#	def add(self, arg):
#		if isinstance(arg, basestring):
#			arg = [int(x) for x in arg.split('.')]
#		return ObjectID(self._value + tuple(arg))
	def __eq__(self, other):
		return self._value == other._value if isinstance(other, ObjectID) else NotImplemented
	def __ne__(self, other):
		return self._value != other._value if isinstance(other, ObjectID) else NotImplemented
	def __hash__(self):
		return hash(self._value)
	def __len__(self):
		return len(self._value)
	def __getitem__(self, idx):
		return self._value[idx]
	def __str__(self):
		return '.'.join([str(n) if n is not None else '' for n in self._value])
	def __repr__(self):
		return 'OID({!r})'.format(str(self))
OID = ObjectID

class Sequence(list):
	__slots__ = []
#	def __getitem__(self, idx):
#		try:
#			return list.__getitem__(self, idx)
#		except IndexError:
#			return None
#	def __getslice__(self, idx, jdx):
#		length = len(self)
#		if jdx > length and jdx != sys.maxint:
#			return list.__getslice__(self + (None,)*(jdx - length), idx, jdx)
#		else:
#			return list.__getslice__(self, idx, jdx)
#	def get_item(self, idx, default=None):
#		try:
#			item =  self[idx]
#		except IndexError:
#			return default
#		else:
#			return item.cast(None) if isinstance(item, TaggedValue) else item
#	def get_slice(self, idx, jdx, default=None):
#		items = [item.cast(None) if isinstance(item, TaggedValue) else item
#				 for item in self[idx:jdx]]
#		if jdx > len(self):
#			items += [default] * (jdx - idx - len(items))
#		return items
	def get_pos(self, pos, count=1, default=None):
		assert count >= 1
		items = self[pos:pos+count]
		assert not any([isinstance(item, TaggedValue) for item in items])
		if len(items) < count:
			items += [default] * (count - len(items))
		return items if count != 1 else items[0]
#		length = len(self)
#		if jdx > length:
#			items = self[idx:] + [default]*(jdx - length)
#		else:
#			items = self[idx:jdx]
#		return [item.cast(None) if isinstance(item, TaggedValue) else item
#				for item in items]
	def find_tag(self, tag):
		if not isinstance(tag, tuple):
			tag = (CONTEXT, tag)
		return next((idx for idx, item in enumerate(self)
					if getattr(item, 'tag', None) == tag), -1)
	def get_tag(self, tag, type=None, default=None, encoding='BER', strict=True):
		if not isinstance(tag, tuple):
			tag = (CONTEXT, tag)
		return next((item.cast(type, encoding, strict) for item in self
					if getattr(item, 'tag', None) == tag), default)

class Set(list):
	__slots__ = []
	def get_tag(self, tag, type=None, default=None, encoding='BER', strict=True):
		if not isinstance(tag, tuple):
			tag = (CONTEXT, tag)
		return next((item.cast(type, encoding, strict) for item in self
					if getattr(item, 'tag', None) == tag), default)

class TaggedValue(object):
	__slots__ = ['tag', '_value']
	def __init__(self, tag, value, explicit=False):
		self.tag = tag if isinstance(tag, tuple) else (CONTEXT, tag)
		self._value = [value] if explicit else value
#		else:
#			self.value = lambda kind: (_decode_primitive(kind, value) if kind is not None else value)
	def __repr__(self):
		return '{}:{!r}'.format(self.tag, self._value)
	def unpack(self):
		tagcls, tagnum = self.tag
		return tagcls, tagnum, self._value
	def cast(self, type, encoding='BER', strict=True):
		if type is None:  # explicit tagged item
			if not isinstance(self._value, list) or len(self._value) != 1:
				raise TypeError('not an ASN.1 explicit tagged type')
			return self._value[0]
		elif isinstance(self._value, list):
			return _decode_constructed(type, self._value, 0, encoding, strict)
		else:
			return _decode_primitive(type, self._value, 0, encoding, strict)
#	def implicit(self, kind):
#		if isinstance(self._value, list):
#			return _decode_constructed(kind, self._value, True)
#		else:
#			return _decode_primitive(kind, self._value, True)
#	def explicit(self):
#		if isinstance(self._value, list) and len(self._value) == 1:
#			return self._value[0]
#		else:
#			raise TypeError('not an ASN.1 explicit tagged type')

class EmbeddedValue(object):
	__slots__ = ['tag', 'ident', 'descriptor', 'value']
	def __init__(self, type, value, abstract=None, transfer=None, descriptor=None):
		if type not in (EXTERNAL, EMBEDDED_PDV, CHARACTER_STRING):
			raise ValueError('type must be one of EXTERNAL, EMBEDDED_PDV, CHARACTER_STRING')
		if abstract is not None and not isinstance(abstract, (ObjectID, int, long)):
			raise TypeError('abstract syntax must be an OID, int, or None')
		if transfer is not None and not isinstance(transfer, ObjectID):
			raise TypeError('transfer syntax must be an OID or None')
		if descriptor is not None and not isinstance(descriptor, basestring):
			raise TypeError('data value descriptor must be a string or None')
		if type == EXTERNAL and abstract is None:
			raise ValueError('invalid identification form for EXTERNAL type')
		self.tag = type
		self.ident = (abstract, transfer)
		self.descriptor = descriptor and ObjectDescriptor(descriptor)
		self.value = value
	def __repr__(self):
		return 'EmbeddedValue({}, {}, {!r}, {!r})'.format(self.tag, self.ident, self.descriptor, self.value)

# ===========================================================================

# ASN.1 helper functions

def btoul(value):
	return int(hexlify(value), 16)

def btosl(value):
	sign = ord(value[0]) & 0x80
	length = len(value)
	value = btoul(value)
	if sign:
		value -= 1 << (length * 8)
	return value

def ultob(value):
	assert value >= 0
	if isinstance(value, long):
		hexval = hex(value)[2:-1]
	else:
		hexval = hex(value)[2:]
	if len(hexval) & 1:
		hexval = '0' + hexval
	return bytes(unhexlify(hexval))
#	hexval = hex(value)[2:-1] if type(value) is long else hex(value)[2:]
#	return unhexlify((b'0' if len(hexval) & 1 else b'') + hexval)

def sltob(value):
	if value < 0:
		value += 0x100 << ((value + 1).bit_length() & 0xFFF8)
		value = ultob(value)
	else:
		value = ultob(value)
		if ord(value[0]) & 0x80:
			value = b'\0' + value
	return value

class ASN1EncodingError(Exception):
	pass

def _decode_error(offset, strict, message):
	if strict:
		raise ASN1EncodingError('error decoding data at offset {}: {}'.format(offset, message))
	elif USE_LOGGING:
		log.warn('error decoding data at offset {}: {}'.format(offset, message))

def _encode_item(item, encoding, strtype, segsize):
	if isinstance(item, TaggedValue):
		tagcls, _tagnum, item = item.unpack()
		tagged = True
#		constr = isinstance(value, list)
	else:
		tagcls = UNIVERSAL
		tagged = False
	ident = (tagcls << 6) & 0xC0
	if hasattr(item, '__iter__') or isinstance(item, EmbeddedValue):
		# Note: this test is sufficient (in Python 2.7 at least) to
		#       distinguish between string types and other sequences.
		tagnum, value = _encode_constructed(item)
		constr = True
	else:
		tagnum, value = _encode_primitive(item, encoding, strtype)
		constr = False
	if tagged:
		tagnum = _tagnum
	if segsize and len(value) > segsize and (tagnum in _string_map or tagnum in (BIT_STRING, OCTET_STRING)):
		assert isinstance(value, bytes)
		r = range(0, len(value), segsize)
		value = [value[i:j] for i, j in zip(r, r[1:] + [None])]
		constr = True
	if not constr:
		assert isinstance(value, bytes)
		content = value
		itemlen = len(value)
	else:
#		assert isinstance(value, (list, tuple))
		ident |= 0x20
		content = []
		itemlen = 0
		for child in value:
			childlen, childval = _encode_item(child, encoding, strtype, segsize)
			if itemlen is not None and childlen is not None:
				itemlen += childlen
			else:
				itemlen = None
			content.append(childval)
#			length += len(elem[0]) + len(elem[1]) + len(elem[2])
		if encoding in ('DER', 'CER') and tagnum == SET:
			# Set component items must be ordered by their tags if this
			# is a SET, or else by their values if this is a SET OF.
			# We don't have enough information to completely determine
			# this ordering, but we will make a best-guess effort.
			if all(ord(elem[0]) & 0xC0 for elem in content):
				content.sort(key=lambda elem: elem[0])
			else:
				content.sort(key=lambda elem: elem[2])
		if encoding == 'CER':
#			content.append((b'\0', b'\0', b'')) # EOC sentinel for indefinite length form
			itemlen = None
#		content = b''.join([b''.join(elem) for elem in content])
#	ident = (tagcls << 6 & 0xC0) | (0x20 if constr else 0)
	if tagnum < 0x1F:
		ident = chr(ident | tagnum)
	else:
		tagnum, byte = divmod(tagnum, 128)
		part = chr(byte)
		while tagnum:
			tagnum, byte = divmod(tagnum, 128)
			part = chr(byte | 0x80) + part
		ident = chr(ident | 0x1F) + part
	if itemlen is None:
		assert isinstance(content, list)
		content.append((b'\0', b'\0', b'')) # EOC sentinel for indefinite length form
		length = b'\x80'
	else:
		if itemlen < 0x80:
			length = chr(itemlen)
		else:
			length = ultob(itemlen)
			length = chr(0x80 | len(length)) + length
		itemlen += len(ident) + len(length)
	return itemlen, (ident, length, content)
#	data.append((ident, hlen, content))
#	return (len(ident) + len(hlen) + length) if length is not None else None
#	data.extend(content)
#	return len(header) + length

def _encode_constructed(item):
	if isinstance(item, (Set, set, frozenset)):
		return SET, item
	elif isinstance(item, (Sequence, list, tuple)):
		return SEQUENCE, item
	elif isinstance(item, dict):
		return SET, item.items()
	elif isinstance(item, EmbeddedValue):
		abstract, transfer = item.ident
		if item.tag == EXTERNAL:
			if transfer is None:
				value = [abstract]
			else:
				value = [transfer, abstract]
			if item.descriptor:
				value.append(item.descriptor)
			if isinstance(item.value, BitString):
				value.append(TaggedValue(2, item.value))
			elif isinstance(item.value, bytes):
				value.append(TaggedValue(1, item.value))
			else:
				value.append(TaggedValue(0, item.value, True))
		else:
			if isinstance(abstract, ObjectID):
				if transfer is not None:
					ident = TaggedValue(0, [abstract, transfer])
				else:
					ident = TaggedValue(1, abstract)
			elif isinstance(abstract, (int, long)):
				if transfer is None:
					ident = TaggedValue(2, abstract)
				else:
					ident = TaggedValue(3, [abstract, transfer])
			else:
				if transfer is not None:
					ident = TaggedValue(4, transfer)
				else:
					ident = TaggedValue(5, None)
			value = [ident, item.value]
		return item.tag, value
	else:
		raise TypeError('invalid ASN.1 constructed type: {}'.format(type(item)))

def _encode_primitive(item, encoding, strtype):
	if item is None:
		return NULL, b''
	elif isinstance(item, bool):
		return BOOLEAN, (b'\xFF' if item else b'\0')
	elif isinstance(item, Enumerated):
		return ENUMERATED, sltob(item)
	elif isinstance(item, (int, long)):
		return INTEGER, sltob(item)
	elif isinstance(item, float):
		s = math.copysign(1.0, item) == -1.0
		if item == 0.0:
			value = b'\x43' if s else b''
		elif math.isinf(item):
			value = b'\x41' if s else b'\x40'
		elif math.isnan(item):
			value = b'\x42'
		else:
			m, e = math.frexp(math.fabs(item))
			assert 0.5 <= m < 1
			i = 1
			while True:
				n = math.ldexp(m, i)
				if n.is_integer():
					break
				i += 1
			e -= i
			assert -1024 <= e <= 1024
			assert int(n) & 1 == 1
			e = sltob(e)
			n = ultob(int(n))
			byte = chr(0x80 | (0x40 if s else 0) | (len(e) - 1))  # binary, base = 2, scaling factor = 0
			value = byte + e + n
		return REAL, value
	elif isinstance(item, BitString):
		if encoding in ('CER', 'DER') and pad:
			assert len(item) > 0
			mask = (1 << pad) - 1
			value = chr(item.pad) + item[:-1] + chr(ord(item[-1]) & ~mask)
		else:
			value =	 chr(item.pad) + item
		return BIT_STRING, value
	elif isinstance(item, bytes):
		return OCTET_STRING, item
	elif isinstance(item, ObjectID):
		assert len(item) >= 2
		if item[0] is None:
			tag = RELATIVE_OID
			item = item[1:]
		else:
			tag = OBJECT_IDENTIFIER
			item = (item[0]*40 + item[1],) + item[2:]
		value = []
		for valn in item:
			valn, byte = divmod(valn, 128)
			part = chr(byte)
			while valn:
				valn, byte = divmod(valn, 128)
				part = chr(byte | 0x80) + part
			value.append(part)
		return tag, b''.join(value)
	elif isinstance(item, IRIString):
		tag = OID_IRI if item.startswith('/') else RELATIVE_OID_IRI
		return tag, item.encode('utf-8')
	elif isinstance(item, unicode):
		try:
			return item.tag, item.encode(item.encoding)
		except AttributeError:
			if strtype is not None:
				return strtype, item.encode(_string_map[strtype].encoding)
			elif ord(max(item)) < 128:
				return IA5_STRING, item.encode(IA5String.encoding)
			else:
				return GENERAL_STRING, item.encode(GeneralString.encoding)
	elif isinstance(item, (date, time)):
		if isinstance(item, datetime):
			if item.tzinfo is TimeZone.UTC:
				tag = UTC_TIME
			elif item.tzinfo:
				tag = GENERALIZED_TIME
			else:
				tag = DATE_TIME
		elif isinstance(item, date):
			tag = DATE
		elif isinstance(item, time):
			tag = TIME_OF_DAY
		format, fmtlen, aware = _datetime_map[tag]
		if tag == GENERALIZED_TIME and item.microsecond:
			format += '{}'
			frac = str(item.microsecond / 1000000.0)[1:]
		else:
			frac = None
		if aware:
			assert item.tzinfo is not None
			if encoding in ('CER', 'DER'):
				item = item.astimezone(TimeZone.Zulu)
			if item.utcoffset():
				format += '%z'
			else:
				format += 'Z'
		return tag, item.strftime(format).format(frac)
	elif isinstance(item, timedelta):
		d = item.days
		h, s = divmod(item.seconds, 3600)
		m, s = divmod(s, 60)
		return DURATION, b'{}DT{}H{}M{}S'.format(d, h, m, s)
	else:
		raise TypeError('invalid ASN.1 primitive type: {}'.format(type(item)))

def _decode_item(file, offset, encoding, strict):
	itemlen = [0]
	def readn(length):
		value = file.read(length)
		if len(value) != length:
			_decode_error(offset, strict, 'insufficient data')
			raise StopIteration
		itemlen[0] += length
		return value
#	ident = ord(data[offset])
#	offset += 1
	ident = ord(readn(1))
	tagnum = ident & 0x1F
	tagcls = ident >> 6
	constr = bool(ident & 0x20)
	if tagnum == 0x1F:
		tagnum = 0
		while True:
			byte = ord(readn(1))
#		while offset < len(data):
#			byte = ord(data[offset])
#			offset += 1
			tagnum = (tagnum << 7) | (byte & 0x7F)
			if byte & 0x80 == 0:
				break
		if tagnum < 31:
			_decode_error(offset, strict, 'invalid identifier form')
#		else:
#			if strict:
#				raise ValueError('invalid ASN.1 data identifier')
#			return None, len(data)
	length = ord(readn(1))
#	length = ord(data[offset])
#	offset += 1
#	if not (length & 0x80):  # definite short form
#		endidx = offset + length
#	else:
	if length & 0x80:
		length &= 0x7F
		if length:  # definite long form
#			endidx = offset + length
			if length == 0x7F:
				_decode_error(offset, strict, 'invalid long form length')
			length = btoul(readn(length))
			if length <= 0x7F and encoding in ('CER', 'DER'):
				_decode_error(offset, strict, 'invalid long form length')
#			length = btol(data[offset:endidx])
#			offset = endidx
#			endidx = offset + length
		else:  # indefinite form
			length = None
#			endidx = len(data)
#	if strict and endidx > len(data):
#		raise ValueError('invalid ASN.1 data length')
	if not constr:
		if length is None:
			_decode_error(offset, strict, 'invalid primitive type length')
			raise StopIteration
		value = readn(length)
	else:
		if encoding == 'CER' and length is not None:
			_decode_error(offset, strict, 'invalid definite length form')
		if encoding == 'DER' and length is None:
			_decode_error(offset, strict, 'invalid indefinite length form')
		value = []
		try:
			while length is None or length > 0:
				childlen, childval = _decode_item(file, offset + itemlen[0], encoding, strict)
				value.append(childval)
				itemlen[0] += childlen
				if length is not None:
					length -= childlen
		except StopIteration:
			if length is not None:
				_decode_error(offset, strict, 'invalid definite length form')
		else:
			assert length is not None
			if length != 0:
				_decode_error(offset, strict, 'invalid constructed type length')
#		if length is None:
#			endidx = offset
#			if strict and item is not StopIteration:
#				raise ValueError('invalid ASN.1 indefinite length form')
#		else:
#			if strict and offset != endidx:
#				raise ValueError('invalid ASN.1 constructed type length')
	if tagcls != UNIVERSAL:
		itemval = TaggedValue((tagcls, tagnum), value)
	elif constr:
		itemval = _decode_constructed(tagnum, value, offset, encoding, strict)
	else:
		itemval = _decode_primitive(tagnum, value, offset, encoding, strict)
	return itemlen[0], itemval
#	return item, endidx

def _decode_constructed(tag, value, offset, encoding, strict):
	assert isinstance(value, list)
	if tag == SEQUENCE:
		return Sequence(value)
	elif tag == SET:
#		print 'dict check'
#		for item in value:
#			if isinstance(item, Sequence):
#				print type(item), len(item), item[0].__hash__
#			else:
#				print type(item)
		if all([isinstance(item, Sequence) and len(item) == 2 and 
				item[0].__hash__ for item in value]):
			return dict(value)
		elif all([item.__hash__ for item in value]):
		   return set(value)
		else:
			return Set(value)
	elif tag == EXTERNAL:
		idx = 0
		abstract = transfer = descriptor = None
		if isinstance(value[idx], ObjectID):
			abstract = value[idx]
			idx += 1
		if isinstance(value[idx], (int, long)):
			transfer = abstract
			abstract = value[idx]
			idx += 1
		if isinstance(value[idx], ObjectDescriptor):
			descriptor = value[idx]
			idx += 1
		tagcls, tagnum = value[idx].tag
		if tagnum == 0:
			value = value[idx].cast(None)
		elif tagnum == 1:
			value = value[idx].cast(OCTET_STRING, encoding, strict)
		elif tagnum == 2:
			value = value[idx].cast(BIT_STRING, encoding, strict)
		return EmbeddedValue(EXTERNAL, value, abstract, transfer, descriptor)
	elif tag in (EMBEDDED_PDV, CHARACTER_STRING):
		ident, value = value
		tagcls, tagnum = ident.tag
#		print 'yoo-hoo', ident, value
		if tagnum in (0, 3):
			abstract, transfer = ident.cast(SEQUENCE, encoding, strict)
		elif tagnum == 1:
			abstract, transfer = ident.cast(OBJECT_IDENTIFIER, encoding, strict), None
		elif tagnum == 2:
			abstract, transfer = ident.cast(INTEGER, encoding, strict), None
		elif tagnum == 4:
			abstract, transfer = None, ident.cast(OBJECT_IDENTIFIER, encoding, strict)
		else:
			abstract = transfer = None
		return EmbeddedValue(tag, value, abstract, transfer)
	elif tag == BIT_STRING:
		if encoding == 'DER':
			_decode_error(offset, strict, 'invalid constructed BIT_STRING')
		if all([isinstance(item, BitString) for item in value]):
			return BitString(b''.join(value), value[-1].pad if value else 0)
	elif tag == OCTET_STRING:
		if encoding == 'DER':
			_decode_error(offset, strict, 'invalid constructed OCTET_STRING')
		if all([isinstance(item, bytes) for item in value]):
			return b''.join(value)
	elif tag in _string_map:
		cls = _string_map[tag]
		if encoding == 'DER':
			_decode_error(offset, strict, 'invalid constructed {}'.format(cls.__name__))
		if all([isinstance(item, bytes) for item in value]):
#			value = b''.join(value)
			try:
				return cls(b''.join(value), cls.codec)
			except UnicodeError:
				pass
#				_decode_error(offset, strict, 'invalid {}: {!r}'.format(cls.__name__, value))
#				return cls(value, cls.encoding, errors='replace')
	_decode_error(offset, strict, 'invalid constructed type {}: {}'.format(tag, value[:50]))
	return TaggedValue((UNIVERSAL, tag), value)

def _decode_primitive(tag, value, offset, encoding, strict):
	assert isinstance(value, bytes)
	if tag == EOC:
		if value:
			_decode_error(offset, strict, 'invalid EOC: {!r}'.format(value))
		raise StopIteration
	elif tag == NULL:
		if not value:
#			_decode_error(offset, strict, 'invalid NULL: {!r}'.format(value))
			return None
	elif tag == BOOLEAN:
		if len(value) == 1:
#			_decode_error(offset, strict, 'invalid BOOLEAN: {!r}'.format(value))
#			value = b'\0'
			return value != b'\0'
	elif tag == ENUMERATED:
		if value:
			return Enumerated(btosl(value))
	elif tag == INTEGER:
		if value:
			return btosl(value)
	elif tag == REAL:
		if not value:
			return 0.0
		byte = ord(value[0])
		kind = byte >> 6
		if kind == 0:  # decimal encoding
			return float(value[1:])
		elif kind == 1:  # special value
			if len(value) != 1:
				pass
			elif byte == 0x40:
				return float('+inf')
			elif byte == 0x41:
				return float('-inf')
			elif byte == 0x42:
				return float('nan')
			elif byte == 0x43:
				return -0.0
		else:
			s = -1 if (byte & 0x40) else +1
			b = (byte >> 4) & 0x03
			f = (byte >> 2) & 0x03
			i = (byte & 0x03) + 2
			e = btosl(value[1:i])
			n = btoul(value[i:])
			m = s * math.ldexp(n, f)
			if b == 0:  # base 2
				return math.ldexp(m, e)
			elif b == 1:  # base 8
				return m * math.pow(8, e)
			elif b == 2:  # base 16
				return m * math.pow(16, e)
	elif tag == BIT_STRING:
		if encoding == 'CER' and len(value) > 1000:
			_decode_error(offset, strict, 'invalid primitive BIT_STRING')
		if value:
			pad = ord(value[0])
			if pad <= 7 and (pad == 0 or len(value) > 1):
#				_decode_error(offset, strict, 'invalid BIT_STRING: {!r}'.format(value))
				return BitString(value[1:], pad)
	elif tag == OCTET_STRING:
		if encoding == 'CER' and len(value) > 1000:
			_decode_error(offset, strict, 'invalid primitive OCTET_STRING')
		return bytes(value)
	elif tag in (OBJECT_IDENTIFIER, RELATIVE_OID):
		oid = []
		valn = 0
		for byte in value:
			byte = ord(byte)
			valn = (valn << 7) | (byte & 0x7F)
			if byte & 0x80 == 0:
				oid.append(valn)
				valn = 0
		if oid and valn == 0:
#			_decode_error(offset, strict, 'invalid OBJECT_IDENTIFIER: {!r}'.format(value))
			if tag == OBJECT_IDENTIFIER:
#				first = oid[0]
	#			if strict and len(oid) < 1:
	#				raise ValueError('invalid ASN.1 object identifier: {!r}'.format(value))
				x = min(oid[0]//40, 2)
				y = oid[0] - x*40
				return ObjectID([x, y], oid[1:])
			else:
				return ObjectID([None], oid)
	elif tag in (OID_IRI, RELATIVE_OID_IRI):
		try:
			return IRIString(value, 'utf-8')
		except UnicodeError:
			pass
	elif tag in _string_map:
		cls = _string_map[tag]
		if encoding == 'CER' and len(value) > 1000:
			_decode_error(offset, strict, 'invalid primitive {}'.format(cls.__name__))
		try:
			return cls(value, cls.encoding)
		except UnicodeError:
			pass
#			_decode_error(offset, strict, 'invalid {}: {!r}'.format(cls.__name__, value))
#			return cls(value, cls.encoding, errors='replace')
	elif tag in _datetime_map:
		format, fmtlen, aware = _datetime_map[tag]
		if aware:
			value, tzone = TimeZone.split(value)
			if (tag == UTC_TIME and tzone is None) or (encoding in ('CER', 'DER') and tzone is not TimeZone.Zulu):
				_decode_error(offset, strict, 'invalid time zone: {!r}'.format(value))
			if tzone is None:
				tzone = TimeZone.UTC if tag == UTC_TIME else TimeZone.Local
		if fmtlen and fmtlen > len(value):
			if encoding in ('CER', 'DER'):
				_decode_error(offset, strict, 'invalid time value: {!r}'.format(value))
			format = format[:len(value)-fmtlen]
		if tag == GENERALIZED_TIME:
			value, _, frac = value.partition('.')
		try:
			value = datetime.strptime(value, format)
		except ValueError:
			pass
#			_decode_error(offset, strict, 'invalid time value: {!r}'.format(value))
		else:
			if aware:
				value = value.replace(tzinfo=tzone)
			if tag == UTC_TIME:
				value = value.astimezone(TimeZone.UTC)
			elif tag == DATE:
				value = value.date()
			elif tag == TIME_OF_DAY:
				value = value.time()
			elif tag == GENERALIZED_TIME and frac:
				frac = float('.'  + frac)
				if len(format) == 12:
					value += timedelta(seconds=frac)
				elif len(format) == 10:
					value += timedelta(minutes=frac)
				elif len(format) == 8:
					value += timedelta(hours=frac)
				elif len(format) == 6:
					value += timedelta(days=frac)
			return value
	elif tag == DURATION:
#		dure = re.compile(r'(?:(\d+)W)?(?:(\d+)D)?(?:T(?:(\d+)H)?(?:(\d+)M)?(?:(\d+)S)?)?')
		match = _duration_re.match(value)
		if match.lastindex:
			w, d, h, m, s = match.groups(0)
			return timedelta(weeks=w, days=d, hours=h, minutes=m, seconds=s)
#	else:
#		if strict:
#			raise ValueError('invalid ASN.1 primitive type tag: {}'.format(tag))
#		return TaggedValue(0, tag, False, value)
	_decode_error(offset, strict, 'invalid primitive type {}: {}'.format(tag, value))
	return TaggedValue((UNIVERSAL, tag), value)
